package leetcode_day._2021._202105._2131;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/29 19:54
 * 元素和为目标值的子矩阵数量
 * 算法：前缀和(动态规划得出)  哈希表
 * 前缀和 --- O(m * m * n * n)
 * 之前用两个点
 * 现在用三条边
 */
public class _29_1074 {

    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        int ans = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                for (int p = i; p <= m; p++)
                    for (int q = j; q <= n; q++)
                        if (pre[p][q] - pre[p][j - 1] - pre[i - 1][q] + pre[i - 1][j - 1] == target) ++ans;
        return ans;
    }

    public int numSubmatrixSumTarget_perfect(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int[][] pre = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
        int ans = 0;
        for (int top = 1; top <= m; top++)
            for (int bot = top; bot <= m; bot++) {
                Map<Integer, Integer> map = new HashMap<>();
                for (int r = 1; r <= n; r++) {
                    int right = pre[bot][r] - pre[top - 1][r];
                    if (right == target) ++ans;
                    if (map.containsKey(right - target)) ans += map.get(right - target);
                    map.put(right, map.getOrDefault(right, 0) + 1);
                }
            }
        return ans;
    }

}
